

#include <iostream>
#include <list>
#include <vector>
#include <queue>
using namespace std;

 struct ListNode 
 {
	int val;
	struct ListNode *next;
	ListNode(int x) : val(x), next(nullptr) {}
 };
 
 class Solution
 {
     using Node = ListNode;

 public:
     ListNode* mergeKLists(vector<ListNode*>& lists)
     {
         if (1 == lists.size() && !lists[0])
             return nullptr;

         Node* guard = new Node(1001);
         Node* tail = guard;
         priority_queue<Node*, vector<Node*>, comp> pq;

         for (auto e : lists)
         {
             if (e)
                 pq.push(e);
         }

         for (Node* cur = nullptr; pq.size();)
         {
             cur = pq.top();

             tail->next = cur;
             tail = tail->next;
             pq.pop();

             if (cur && cur->next)
             {
                 pq.push(cur->next);
             }
         }
         tail = guard->next;
         delete guard;

         return tail;
     }

     ListNode* reverseKGroup(ListNode* head, int k)
     {
         using Node = ListNode;

         if (1 == k || !head || !head->next)
             return head;

         int cnt = 0;
         Node* cur = head;

         while (cur)
         {
             ++cnt;
             cur = cur->next;
         }
         cnt /= k;

         cur = head;
         Node* guard = new Node(-1);
         Node* tmptail = guard, * tmp = nullptr;

         for (int i = 0; i < cnt; ++i)
         {
             tmp = cur;

             for (int j = 0; j < k; ++j)
             {
                 Node* next = cur->next;

                 cur->next = tmptail->next;
                 tmptail->next = cur;
                 cur = next;
             }
             tmptail = tmp;
         }
         if (cur)
             tmptail->next = cur;

         cur = guard->next;
         delete guard;

         return cur;
     }

     vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k)
     {
         int m = mat.size(), n = mat[0].size();
         vector<vector<int>> res(m, vector<int>(n));
         vector<vector<int>> dp(m + 1, vector<int>(n + 1));

         for (int i = 1; i <= m; ++i)
         {
             for (int j = 1; j <= n; ++j)
             {
                 dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
             }
         }

         for (int i = 0; i < m; ++i)
         {
             for (int j = 0; j < n; ++j)
             {
                 res[i][j] = dp[min(i + 1 + k, m)][min(j + 1 + k, n)] - dp[min(i + 1 + k, m)][max(j - k, 0)] - dp[max(i - k, 0)][min(j + 1 + k, n)] + dp[max(i - k, 0)][max(j - k, 0)];
             }
         }

         return res;
     }

 private:
     struct comp
     {
         bool operator()(Node* x, Node* y)
         {
             return x->val > y->val;
         }
     };
 };

 void Test1()
 {
     int k = 3;
     vector<vector<int>> vv{ {67, 64, 78},{99, 98, 38},{82, 46, 46},{6, 52, 55},{55, 99, 45} };

     Solution().matrixBlockSum(vv, k);
 }

int main()
{
    Test1();

	return 0;
}